# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        # 分割链表
        def getMid(head):
            slow = fast = head
            prev = None
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next
            prev.next = None  # 断开链接
            return slow
        
        # 合并两个有序链表
        def merge(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next
            
            # 连接剩余部分
            curr.next = l1 or l2
            return dummy.next
        
        # 递归分割和合并
        mid = getMid(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        
        return merge(left, right)
